package com.hy.dp.bagProblem.ZeroOnebag;

public class BagProblem {

    /**
     * 01 背包
     *
     * 有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，
     * 得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。
     *
     * @param weight
     * @param value
     * @param bagSize
     */

    public static void testWeightBagProblem(int [] weight,int [] value,int bagSize){
        int wlen = weight.length,value0 = 0;
        //定义dp数组：dp[i][j]表示背包容量为j时，前i个物品能获得的最大价值
        int [][] dp = new int[wlen + 1][bagSize + 1];
        // 初始化：背包容量为0时，能获得的价值都为0
        for (int i = 0; i <= wlen; i++) {
            dp[i][0] = value0;
        }
        // 遍历 遍历顺序：先遍历物品，再遍历背包容量
        for (int i = 1; i <= wlen; i++) {
            for (int j = 1; j <= bagSize; j++) {
            // 实就是当物品i的重量大于背包j的重量时，物品i无法放进背包中，所以被背包内的价值依然和前面相同。
             if (j < weight[i -1]){
                 dp[i][j] = dp[i-1][j];
             }else {
                 // dp[i - 1][j - weight[i]] 为背包容量为j - weight[i]的时候不放物品i的最大价值，
                 // 那么dp[i - 1][j - weight[i]] + value[i] （物品i的价值），就是背包放物品i得到的最大价值
                 dp[i][j] = Math.max(dp[i - 1][j],dp[i-1][j -weight[i - 1]] + value[i - 1]);
             }
            }
        }
        // 遍历 dp
        for (int i = 0; i <= wlen; i++) {
            for (int j = 0; j <= bagSize; j++) {
                System.out.print(dp[i][j]+ "  ");
            }
            System.out.println("");
        }


    }

    public static void main(String[] args) {
        int [] weight = {1, 3, 4};
        int [] value = {15, 20, 30};
        int bagSize = 4;
        BagProblem.testWeightBagProblem(weight,value,bagSize);
    }
}
